package nowcoder.offer;

/**
 * 矩阵中的路径
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-08-30 15:12
 */
public class HasPath {

    char[][] matrix;
    int rows;
    int cols;
    char[] str;
    int[][] path;
    public boolean solution(char[] matrix,int rows,int cols,char[] str){
        if (matrix == null || matrix.length == 0 || rows ==0 || cols == 0 || str == null || str.length == 0) return false;
        this.matrix = new char[rows][cols];
        int k = 0;
        this.rows = rows;
        this.cols = cols;
        this.str = str;
        this.path = new int[rows][cols]; //记录遍历结果
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                this.matrix[i][j] = matrix[k++];
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (search(i,j,0))
                    return true;
            }
        }
        return false;
    }

    public boolean search(int i,int j,int index){
        if (i < 0 || i >=rows || j < 0 || j >= cols || matrix[i][j] != str[index] || path[i][j] == 1) return false;
        if (index == str.length-1) return true;
        path[i][j] = 1;
        if (search(i,j+1,index+1)
                ||search(i+1,j,index+1)
                ||search(i,j-1,index+1)
                ||search(i-1,j,index+1)){
            return true;
        }
        path[i][j] = 0; //还原现场
        return false;
    }


    public static void main(String[] args) {
        System.out.println(new HasPath().solution("abcesfcsadee".toCharArray(), 3, 4, "abcesee".toCharArray()));
    }
}
